﻿// Jinx AJAX Framework
// Copyright (C) 2008 Blake Hegerle
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Formality;
using Core;

namespace Formality.FormalSystem.Parser
{
    internal class PrecedenceParser<T>
    {
        public override string ToString()
        {
            return (from Op in Stack
                    select Op.ToString()).Join(", ");
        }

        internal T Parse(Func<string, IEnumerable<T>, T> Converter)
        {
            Util.CoEnumerate(Operands, Operators, (Operand, OperatorSymbol) =>
            {
                var Operator = OperatorMap[OperatorSymbol];

                var Infix = new Operator<T>(Operator);

                /* First, we have to be preparred for the case in which the current operator
                 * is of LOWER precedence than the operators on the top of the stack. 
                 * 
                 * We need to go down the stack until we find an operator of equal-or-less
                 * precedence. As we go, we add a new operand to each operator we pop:
                 * the operator that was originally on top gets the current operator, while
                 * the others get the operator that used to be on top of itself.
                 */
                Operator<T> SubInfix = null;

                Expression<T> Prev = new Term<T>(Operand);

                while (Stack.Count > 0 && Operator.Precedence < Top.Precedence)
                {
                    SubInfix = Stack.Pop();
                    SubInfix.AddOperand(Prev);
                    Prev = SubInfix;
                }

                // Add the operand to our new operator
                Infix.AddOperand(Prev);

                // Are we initializing the stack?
                if (Stack.Count == 0)
                    Stack.Push(Infix);
                else
                {
                    /* If the current operator is of equal precedence to the operator on
                     * the top of the stack, we need to merge it with that operator. Otherwise,
                     * we just push.
                     */

                    if (Infix.Precedence == Top.Precedence)
                        Top.AddOperands(Infix.Operands);
                    else
                        Stack.Push(Infix);
                }
            });

            // Add the final operand
            Top.AddOperand(new Term<T>(Operands.Last()));

            // Collapse the stack: this is much like the while loop above.
            while (Stack.Count > 1)
            {
                var Higher = Stack.Pop();
                Top.AddOperand(Higher);
            }

            return Stack.Single().Convert(Converter);
        }

        internal IEnumerable<T> Operands { get; set; }
        internal IEnumerable<string> Operators { get; set; }
        internal Dictionary<string, Operator> OperatorMap { get; set; }
        internal int OperandPrecedence { get; set; }

        private Operator<T> Top { get { return Stack.Peek(); } }

        private Stack<Operator<T>> Stack = new Stack<Operator<T>>();
    }
}
